1
Fondamenti Geometrici dell'Ottimizzazione Convessa
MATH008Lesson 8
00:00
Immagina di navigare un paesaggio complesso in cui il tuo obiettivo è trovare il punto più vicino alla sicurezza. Nel linguaggio dell'ottimizzazione, questa 'sicurezza' è un insieme $C$, e l'atto di trovare il punto più vicino è una proiezione. Sebbene l'intuizione suggerisca che esista sempre un singolo punto 'più vicino', la realtà matematica è più sfumata. La base geometrica dell'ottimizzazione convessa si fonda sulla formalizzazione della 'vicinanza', andando oltre l'intuizione euclidea per rappresentazioni funzionali rigorose come le funzioni indicatrice e di supporto.

1. Proiezioni e Distanze

La distanza da un punto $x_0$ a un insieme $C$ è definita come l'estremo inferiore di tutte le distanze possibili ai punti all'interno dell'insieme:

$\text{dist}(x_0, C) = \inf\{\|x_0 - x\| \mid x \in C\}$

L'ottimizzatore specifico che raggiunge questa distanza è l'operatore di proiezione:

$P_C(x_0) = \text{argmin}\{\|x - x_0\| \mid x \in C\}$

Per un semplice iperpiano definito da $a^T x = b$, la proiezione ha una splendida soluzione in forma chiusa: $P_C(x_0) = x_0 + (b - a^T x_0)a/\|a\|_2^2$. Tuttavia, per insiemi generali, questo rimane un problema di ottimizzazione vincolato: minimizza $\|x - x_0\|$ soggetto a $f_i(x) \leq 0$ e $Ax = b$.

2. Geometria Funzionale

Per trattare i vincoli geometrici come componenti oggettivi, utilizziamo due potenti 'specchi' funzionali:

  • La Funzione Indicatrice $I_C(x)$: $I_C(x) = \begin{cases} 0 & x \in C \\ +\infty & x \notin C \end{cases}$. Questo riduce la geometria a una penalità numerica.
  • La Funzione di Supporto $S_C(x)$: $S_C(x) = \sup_{y \in C} x^T y$. Questa caratterizza l'insieme attraverso i suoi iperpiani di confine in ogni direzione.
Teorema: Teorema di Motzkin

Un insieme non vuoto e chiuso $C \in \mathbf{R}^n$ è un insieme di Chebyshev (che possiede una proiezione unica per ogni $x_0$) se e solo se è convesso.

Schema di Dimostrazione (Unicità)

Supponiamo che $C$ sia convesso e che la norma sia strettamente convessa. Se ci fossero due punti distinti più vicini $u, v \in C$ con $\|u - x_0\| = \|v - x_0\| = d$, allora il loro punto medio $w = (u+v)/2$ sarebbe in $C$ (per convessità).

Per la stretta convessità della norma: $\|w - x_0\| = \|\frac{1}{2}(u - x_0) + \frac{1}{2}(v - x_0)\| < \frac{1}{2}\|u - x_0\| + \frac{1}{2}\|v - x_0\| = d$.

Questo contraddice l'ipotesi che $d$ fosse la distanza minima. Pertanto, la proiezione deve essere unica.

Avvertimento 8.4: Dipendenza dalla Norma

Spesso costruiamo un iperpiano separante usando: $(P_C(x_0) - x_0)^T (x - (1/2)(x_0 + P_C(x_0))) = 0$. Attenzione! Questa costruzione specifica è valida solo per la norma euclidea. Le norme generali richiedono trattamenti più fini dell'ortogonalità.

🎯 Principale Intuizione
La convessità è il 'collante' che garantisce stabilità nell'ottimizzazione geometrica. Senza di essa, anche il semplice compito di 'trovare il punto più vicino' può portare a soluzioni multiple e contrastanti, causando instabilità algoritmica.